class Solution {
    /*
        思路1：借助List容器
            空间复杂度O(N)
    */
    public ListNode reverseBetween(ListNode head, int left, int right) {
        List<ListNode> list = new ArrayList();
        // 虚节点
        ListNode res = new ListNode(-1);
        list.add(res);
        // 遍历
        while(head!=null){
            list.add(head);
            head = head.next;
        }
        // 取出List的值
        for(int i=1; i<left; i++){
            res.next = list.get(i);
            res = list.get(i);
        }
        for(int i=right; i>=left; i--){
            res.next = list.get(i);
            res = list.get(i);
        }
        for(int i=right+1; i<list.size(); i++){
            res.next = list.get(i);
            res = list.get(i);
        }
        res.next = null;
        return list.get(0).next;
    }
}
class Solution {
    /*
        思路2：头插法
            加入要求把节点A后面的链表逆置，则每次把要逆置的节点插入到A的后面就行
    */
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode vNode = new ListNode(-1,head); // vNode.next = head;
        ListNode tot = vNode; // tot：需反转链表的前一个位置
        for(int i=1; i<left; i++){
            tot = head;
            head = head.next;
        }
        // System.out.println(tot.val);
        ListNode tail = tot.next;// 用于记录逆置链表的最后一个位置
        // 依次把需要逆置的节点插入到tot的后面
        for(int i=left; i<=right; i++){
            ListNode t1 = tot.next;
            ListNode t2 = head.next;
            tot.next = head;
            head.next = t1;
            head = t2;
        }
        tail.next = head; // 用于连接逆置链表后面不需要逆置的链表
        return vNode.next;
    }
}